class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        res = 0
        left = [0]*(len(height)+2)
        right = [0]*(len(height)+2)
        for i in range(1,len(height)+1):
            left[i] = max(left[i-1], height[i-1])
        for i in range(len(height),0,-1):
            right[i] = max(right[i+1], height[i-1])
            res += min(left[i], right[i])-height[i-1]
        return res

test=Solution()
print(test.trap([0,1,0,2,1,0,1,3,2,1,2,1]))

